#include <stdio.h>

void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void insertion_sort(int unsorted_array[], int num_elements) {
    for (int j = 1; j < num_elements; j++) {
        int key = unsorted_array[j];
        int i = j - 1;
        while (i >= 0 && key < unsorted_array[i]) {
            unsorted_array[i + 1] = unsorted_array[i];
            i--;
        }
        unsorted_array[i + 1] = key;
        print_array(unsorted_array, num_elements);
    }
}


int partition(int L[], int low, int  high, int total_num_elements) {//分割
    int temp = L[low];
    int pivot = L[low];
    while (low < high) {
        while (low < high && L[high] >= pivot) {
            --high;
        }
        L[low] = L[high];
        while (low < high && L[low] <= pivot) {
            ++low;
        }
        L[high] = L[low];
    }
    L[low] = temp;
    print_array(L, total_num_elements);
    return low;
}
void QSort(int L[], int low, int  high, int total_num_elements) {
    if (low < high) {
        int  pivotpos = partition(L, low, high, total_num_elements);

        QSort(L, low, pivotpos - 1, total_num_elements);
        QSort(L, pivotpos + 1, high, total_num_elements);

    }
}

void quick_sort(int unsorted_array[], int num_elements) {
    int low = 0, high = num_elements - 1;
    QSort(unsorted_array, low, high, num_elements);
}


void max_heap_down(int a[], int start, int end)
{
    int c = start;
    int l = 2 * c + 1;//start的左孩子索引
    int tmp = a[c];
    for (; l <= end; c = l, l = 2 * l + 1)//将c设置为其左孩子，l设置为右孩子
    {
        if (l < end && a[l] < a[l + 1])//如果右孩子小于end，并且,右孩子小于左孩子
            l++;       //将l改为左孩子索引
        if (tmp >= a[l])//如果c的孩子中较大的元素大于父亲节点
            break;   //则跳出循环
        else           //否则
        {
            a[c] = a[l];//将父亲节点和比自己大的孩子结点交换
            a[l] = tmp;
        }
    }
}
void heap_sort(int unsorted_array[], int num_elements) {
    int i;
    int swap;
    for (i = num_elements / 2 - 1; i >= 0; i--)
        max_heap_down(unsorted_array, i, num_elements - 1);
    for (i = num_elements - 1; i > 0; i--)//设置n-1次循环，因为当n-1个节点都按顺序排好以后，最后一个一定是最小值
    {
        swap = unsorted_array[i];
        unsorted_array[i] = unsorted_array[0];
        unsorted_array[0] = swap;
        print_array(unsorted_array, num_elements);
        max_heap_down(unsorted_array, 0, i - 1);
    }
}